//按摩师
class Solution {
public:
    int massage(vector<int>& nums) 
    {
        //dp[i][0] 不选i位置
        //dp[i][1]  选i位置
        if(nums.empty()) return 0;
        if(nums.size()==1) return nums[0];
        if(nums.size()==2) return max(nums[0],nums[1]);
        int n=nums.size();
        vector<vector<int>>dp(n,vector<int>(2,0));
        dp[0][1]=nums[0];
        dp[1][0]=nums[0];
        dp[1][1]=max(nums[0],nums[1]);
        for(int i=2;i<n;i++)
        {
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=max(dp[i-1][0],max(dp[i-2][0],dp[i-2][1]) )+nums[i];
        }
        return max(dp[n-1][0],dp[n-1][1]);
    }
};
//删除并获得点数

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) 
    {
        const int N=10010;
        int arr[N]={0};
        for(auto e:nums) arr[e]+=e;

        const int n=N;
        //dp[i][0] 不拿数字i dp[i][1] 拿数字i
        vector<vector<int>>dp(n,vector<int>(2,0));
        for(int i=1;i<n;i++)
        {
            dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
            dp[i][1]=dp[i-1][0]+arr[i];
        }
        return max(dp[n-1][0],dp[n-1][1]);
    }
};